home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / gnu / grep / grep.lzh / dfa.c < prev    next >
C/C++ Source or Header  |  1989-03-02  |  59KB  |  2,224 lines
  1. /* dfa.c - determinisitic extended regexp routines for GNU
  2.    Copyright (C) 1988 Free Software Foundation, Inc.
  3.                       Written June, 1988 by Mike Haertel
  4.               Modified July, 1988 by Arthur David Olson
  5.              to assist BMG speedups
  6.  
  7.                NO WARRANTY
  8.  
  9.   BECAUSE THIS PROGRAM IS LICENSED FREE OF CHARGE, WE PROVIDE ABSOLUTELY
  10. NO WARRANTY, TO THE EXTENT PERMITTED BY APPLICABLE STATE LAW.  EXCEPT
  11. WHEN OTHERWISE STATED IN WRITING, FREE SOFTWARE FOUNDATION, INC,
  12. RICHARD M. STALLMAN AND/OR OTHER PARTIES PROVIDE THIS PROGRAM "AS IS"
  13. WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING,
  14. BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  15. FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS TO THE QUALITY
  16. AND PERFORMANCE OF THE PROGRAM IS WITH YOU.  SHOULD THE PROGRAM PROVE
  17. DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR
  18. CORRECTION.
  19.  
  20.  IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW WILL RICHARD M.
  21. STALLMAN, THE FREE SOFTWARE FOUNDATION, INC., AND/OR ANY OTHER PARTY
  22. WHO MAY MODIFY AND REDISTRIBUTE THIS PROGRAM AS PERMITTED BELOW, BE
  23. LIABLE TO YOU FOR DAMAGES, INCLUDING ANY LOST PROFITS, LOST MONIES, OR
  24. OTHER SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE
  25. USE OR INABILITY TO USE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR
  26. DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY THIRD PARTIES OR
  27. A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS) THIS
  28. PROGRAM, EVEN IF YOU HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH
  29. DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY.
  30.  
  31.         GENERAL PUBLIC LICENSE TO COPY
  32.  
  33.   1. You may copy and distribute verbatim copies of this source file
  34. as you receive it, in any medium, provided that you conspicuously and
  35. appropriately publish on each copy a valid copyright notice "Copyright
  36.  (C) 1988 Free Software Foundation, Inc."; and include following the
  37. copyright notice a verbatim copy of the above disclaimer of warranty
  38. and of this License.  You may charge a distribution fee for the
  39. physical act of transferring a copy.
  40.  
  41.   2. You may modify your copy or copies of this source file or
  42. any portion of it, and copy and distribute such modifications under
  43. the terms of Paragraph 1 above, provided that you also do the following:
  44.  
  45.     a) cause the modified files to carry prominent notices stating
  46.     that you changed the files and the date of any change; and
  47.  
  48.     b) cause the whole of any work that you distribute or publish,
  49.     that in whole or in part contains or is a derivative of this
  50.     program or any part thereof, to be licensed at no charge to all
  51.     third parties on terms identical to those contained in this
  52.     License Agreement (except that you may choose to grant more extensive
  53.     warranty protection to some or all third parties, at your option).
  54.  
  55.     c) You may charge a distribution fee for the physical act of
  56.     transferring a copy, and you may at your option offer warranty
  57.     protection in exchange for a fee.
  58.  
  59. Mere aggregation of another unrelated program with this program (or its
  60. derivative) on a volume of a storage or distribution medium does not bring
  61. the other program under the scope of these terms.
  62.  
  63.   3. You may copy and distribute this program or any portion of it in
  64. compiled, executable or object code form under the terms of Paragraphs
  65. 1 and 2 above provided that you do the following:
  66.  
  67.     a) accompany it with the complete corresponding machine-readable
  68.     source code, which must be distributed under the terms of
  69.     Paragraphs 1 and 2 above; or,
  70.  
  71.     b) accompany it with a written offer, valid for at least three
  72.     years, to give any third party free (except for a nominal
  73.     shipping charge) a complete machine-readable copy of the
  74.     corresponding source code, to be distributed under the terms of
  75.     Paragraphs 1 and 2 above; or,
  76.  
  77.     c) accompany it with the information you received as to where the
  78.     corresponding source code may be obtained.  (This alternative is
  79.     allowed only for noncommercial distribution and only if you
  80.     received the program in object code or executable form alone.)
  81.  
  82. For an executable file, complete source code means all the source code for
  83. all modules it contains; but, as a special exception, it need not include
  84. source code for modules which are standard libraries that accompany the
  85. operating system on which the executable file runs.
  86.  
  87.   4. You may not copy, sublicense, distribute or transfer this program
  88. except as expressly provided under this License Agreement.  Any attempt
  89. otherwise to copy, sublicense, distribute or transfer this program is void and
  90. your rights to use the program under this License agreement shall be
  91. automatically terminated.  However, parties who have received computer
  92. software programs from you with this License Agreement will not have
  93. their licenses terminated so long as such parties remain in full compliance.
  94.  
  95.   5. If you wish to incorporate parts of this program into other free
  96. programs whose distribution conditions are different, write to the Free
  97. Software Foundation at 675 Mass Ave, Cambridge, MA 02139.  We have not yet
  98. worked out a simple rule that can be stated here, but we will often permit
  99. this.  We will be guided by the two goals of preserving the free status of
  100. all derivatives our free software and of promoting the sharing and reuse of
  101. software.
  102.  
  103.  
  104. In other words, you are welcome to use, share and improve this program.
  105. You are forbidden to forbid anyone else to use, share and improve
  106. what you give them.   Help stamp out software-hoarding!  */
  107.  
  108. #include <stdio.h>
  109. #include <assert.h>
  110. #include <ctype.h>
  111. #include "dfa.h"
  112.  
  113. #ifdef __STDC__
  114. typedef void *ptr_t;
  115. #else
  116. typedef char *ptr_t;
  117. #endif
  118.  
  119. static void    regmust();
  120.  
  121. static ptr_t
  122. xcalloc(n, s)
  123.      int n;
  124.      size_t s;
  125. {
  126.   ptr_t r = calloc(n, s);
  127.  
  128.   if (r)
  129.     return r;
  130.   else
  131.     regerror("Memory exhausted");
  132. }
  133.  
  134. static ptr_t
  135. xmalloc(n)
  136.      size_t n;
  137. {
  138.   ptr_t r = malloc(n);
  139.  
  140.   assert(n != 0);
  141.   if (r)
  142.     return r;
  143.   else
  144.     regerror("Memory exhausted");
  145. }
  146.  
  147. static ptr_t
  148. xrealloc(p, n)
  149.      ptr_t p;
  150.      size_t n;
  151. {
  152.   ptr_t r = realloc(p, n);
  153.  
  154.   assert(n != 0);
  155.   if (r)
  156.     return r;
  157.   else
  158.     regerror("Memory exhausted");
  159. }
  160.  
  161. #define CALLOC(p, t, n) ((p) = (t *) xcalloc((n), sizeof (t)))
  162. #define MALLOC(p, t, n) ((p) = (t *) xmalloc((n) * sizeof (t)))
  163. #define REALLOC(p, t, n) ((p) = (t *) xrealloc((ptr_t) (p), (n) * sizeof (t)))
  164.  
  165. /* Reallocate an array of type t if nalloc is too small for index. */
  166. #define REALLOC_IF_NECESSARY(p, t, nalloc, index) \
  167.   if ((index) >= (nalloc))              \
  168.     {                          \
  169.       while ((index) >= (nalloc))          \
  170.     (nalloc) *= 2;                  \
  171.       REALLOC(p, t, nalloc);              \
  172.     }
  173.  
  174. /* Stuff pertaining to charsets. */
  175.  
  176. static
  177. tstbit(b, c)
  178.      int b;
  179.      _charset c;
  180. {
  181.   return c[b / INTBITS] & 1 << b % INTBITS;
  182. }
  183.  
  184. static void
  185. setbit(b, c)
  186.      int b;
  187.      _charset c;
  188. {
  189.   c[b / INTBITS] |= 1 << b % INTBITS;
  190. }
  191.  
  192. static void
  193. clrbit(b, c)
  194.      int b;
  195.      _charset c;
  196. {
  197.   c[b / INTBITS] &= ~(1 << b % INTBITS);
  198. }
  199.  
  200. static void
  201. copyset(src, dst)
  202.      const _charset src;
  203.      _charset dst;
  204. {
  205.   int i;
  206.  
  207.   for (i = 0; i < _CHARSET_INTS; ++i)
  208.     dst[i] = src[i];
  209. }
  210.  
  211. static void
  212. zeroset(s)
  213.      _charset s;
  214. {
  215.   int i;
  216.  
  217.   for (i = 0; i < _CHARSET_INTS; ++i)
  218.     s[i] = 0;
  219. }
  220.  
  221. static void
  222. notset(s)
  223.      _charset s;
  224. {
  225.   int i;
  226.  
  227.   for (i = 0; i < _CHARSET_INTS; ++i)
  228.     s[i] = ~s[i];
  229. }
  230.  
  231. static
  232. equal(s1, s2)
  233.      const _charset s1;
  234.      const _charset s2;
  235. {
  236.   int i;
  237.  
  238.   for (i = 0; i < _CHARSET_INTS; ++i)
  239.     if (s1[i] != s2[i])
  240.       return 0;
  241.   return 1;
  242. }
  243.  
  244. /* A pointer to the current regexp is kept here during parsing. */
  245. static struct regexp *reg;
  246.  
  247. /* Find the index of charset s in reg->charsets, or allocate a new charset. */
  248. static
  249. charset_index(s)
  250.      const _charset s;
  251. {
  252.   int i;
  253.  
  254.   for (i = 0; i < reg->cindex; ++i)
  255.     if (equal(s, reg->charsets[i]))
  256.       return i;
  257.   REALLOC_IF_NECESSARY(reg->charsets, _charset, reg->calloc, reg->cindex);
  258.   ++reg->cindex;
  259.   copyset(s, reg->charsets[i]);
  260.   return i;
  261. }
  262.  
  263. /* Syntax bits controlling the behavior of the lexical analyzer. */
  264. static syntax_bits, syntax_bits_set;
  265.  
  266. /* Flag for case-folding letters into sets. */
  267. static case_fold;
  268.  
  269. /* Entry point to set syntax options.